package com.kdg.arithmetic;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 简单选择排序
 * Created by kong on 2018/5/21.
 */
public class SimpleSelectSort {
    private static Logger logger = LoggerFactory.getLogger(StraightInsertionSort.class);

    public static void main(String[] args) throws InterruptedException {
        int a[] = {23, 12, 35, 68, 4, 3, 5, 90};
        selectSortTwo(a);
    }

    /**
     * 打印
     *
     * @param a
     */
    private static void printSort(int[] a) {
        if (a.length > 0) {
            for (int i : a) {
                System.out.print(i + " ");
            }
        }
    }

    /**
     * 简单选择排序
     *
     * @param a
     */
    private static void selectSort(int[] a) throws InterruptedException {
        if (a.length > 0) {
            for (int i = 0; i < a.length; i++) {
                int x = i;  //存放最小值下标
                for (int j = i + 1; j < a.length; j++) {
                    if (a[j] < a[x]) {
                        x = j;
                    }
                }
                swap(a, x, i);
                System.out.println();
            }
        }
    }

    /**
     * 简单选择排序改进--二元选择排序(减少排序次数为原来的一半)
     *
     * @param a
     */
    private static void selectSortTwo(int[] a) throws InterruptedException {
        if (a.length > 0) {
            int n = a.length;
            int i, j, min, max, tmp;
//            for (i = 1; i <= n / 2; i++) {
//                min = i;
//                max = i;
//                for (j = i+1; j <= (n - i); j++) {
//
//                    if (a[j] > a[max]) {
//                        max = j;
//                        continue;
//                    }
//                    if (a[j] < a[min]) {
//                        min = j;
//                    }
//                }
//                swap(a, min, (i - 1));
//                swap(a, max, (n - i));
//            }
//            int i ,j , min ,max, tmp;
            for (i = 0; i < n / 2; i++) {
                min = i; max = i;
                for (j = i ; j < n - i; j++) {
                    if (a[j] > a[max]) {
                        max = j;
                        continue;
                    }
                    if (a[j] < a[min]) {
                        min = j;
                    }
                }
                int maxtmp = 0;
                int mintmp = 0;     //注意:这里不能把a[max],a[min]直接和a[i]和a[n-i-1]调换
                maxtmp = a[max];
                a[max] = a[n-i-1];
                a[n-i-1] = maxtmp;

                mintmp = a[min];
                a[min] = a[i];
                a[i] = mintmp;
//                swap(a, max, (n-i-1));
//                swap(a, min, i);
            }
            printSort(a);
        }
    }

    /**
     * 交换位置
     *
     * @param a 数组
     * @param x 最小元素的下标
     * @param i 目的下标
     */
    private static void swap(int[] a, int x, int i) {
        int d = a[i];
        a[i] = a[x];
        a[x] = d;
    }
}
